{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Optimal Partition of String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partitionString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子字符串的最优划分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，请你将该字符串划分成一个或多个 <strong>子字符串</strong> ，并满足每个子字符串中的字符都是 <strong>唯一</strong> 的。也就是说，在单个子字符串中，字母的出现次数都不超过 <strong>一次</strong> 。</p>\n",
    "\n",
    "<p>满足题目要求的情况下，返回 <strong>最少</strong> 需要划分多少个子字符串<em>。</em></p>\n",
    "\n",
    "<p>注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abacaba\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "两种可行的划分方法分别是 (\"a\",\"ba\",\"cab\",\"a\") 和 (\"ab\",\"a\",\"ca\",\"ba\") 。\n",
    "可以证明最少需要划分 4 个子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ssssss\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：\n",
    "</strong>只存在一种可行的划分方法 (\"s\",\"s\",\"s\",\"s\",\"s\",\"s\") 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [optimal-partition-of-string](https://leetcode.cn/problems/optimal-partition-of-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [optimal-partition-of-string](https://leetcode.cn/problems/optimal-partition-of-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abacaba\"', '\"ssssss\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        nSubs: int = 1\n",
    "        seen: Set[str] = set()\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                seen.add(c)\n",
    "            else:\n",
    "                nSubs += 1\n",
    "                seen = set([c])\n",
    "\n",
    "        return nSubs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=0\n",
    "        for c in s:\n",
    "            if cnt&1<<(ord(c)-ord('a')):\n",
    "                cnt=1<<(ord(c)-ord('a'))\n",
    "                res +=1\n",
    "            else:\n",
    "                cnt |=1<<(ord(c)-ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count = 1\n",
    "        tmp = \"\"\n",
    "        for i in s:\n",
    "            if i in tmp:\n",
    "                count += 1\n",
    "                tmp = i\n",
    "                continue\n",
    "            tmp = tmp + i\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        mp = Counter()\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if len(mp) == 0:\n",
    "                ans += 1\n",
    "                mp[c] = 1\n",
    "                continue\n",
    "            if c in mp:\n",
    "                ans += 1\n",
    "                mp.clear()\n",
    "            mp[c] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ha=[]\n",
    "        count=0\n",
    "        for ch in s:\n",
    "            if ch in ha:\n",
    "                count+=1\n",
    "                ha=[ch]\n",
    "            else:\n",
    "                ha.append(ch)\n",
    "        return count+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=set()\n",
    "        for c in s:\n",
    "            if c not in cnt:\n",
    "                cnt.add(c)\n",
    "            else:\n",
    "                cnt=set()\n",
    "                cnt.add(c)\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        j, cnt, window = 0, 0, []\n",
    "        while j < len(s):\n",
    "            if s[j] in window: \n",
    "                cnt += 1\n",
    "                window = []  \n",
    "            window.append(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        r=0\n",
    "        t=set()\n",
    "        res=0\n",
    "        while r<len(s):\n",
    "            if s[r] not in t:\n",
    "                t.add(s[r])\n",
    "            else:\n",
    "                res+=1\n",
    "                t.clear()\n",
    "                t.add(s[r])\n",
    "            r+=1\n",
    "        return res+1\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=''\n",
    "        for c in s:\n",
    "            if c not in cnt:\n",
    "                cnt +=c\n",
    "            else:\n",
    "                cnt=c\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 使用集合进行辅助\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        total_num = 0\n",
    "        while i < n:\n",
    "            se = set(s[i])\n",
    "            j = i + 1\n",
    "            while j < n:\n",
    "                if s[j] in se:\n",
    "                    # 此时出现重复的，因此需要更新i\n",
    "                    i = j\n",
    "                    total_num += 1\n",
    "                    break\n",
    "                else:\n",
    "                    se.add(s[j])\n",
    "                    j += 1\n",
    "            # 判断j是否为n\n",
    "            if j == n:\n",
    "                total_num += 1\n",
    "                break\n",
    "        return total_num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        st = set()\n",
    "        for c in s:\n",
    "            if c not in st:\n",
    "                st.add(c)\n",
    "            else:\n",
    "                ans += 1\n",
    "                st = {c}\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 1\n",
    "        tmp = ''\n",
    "        for c in s:\n",
    "            if c not in tmp:\n",
    "                tmp += c\n",
    "            else:\n",
    "                tmp = c\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 贪心\n",
    "        ans = 0\n",
    "        m = set()\n",
    "        for c in s:\n",
    "            if c in m:\n",
    "                ans += 1\n",
    "                m.clear()\n",
    "            m.add(c)\n",
    "            \n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        nowset = set()\n",
    "        left = 0\n",
    "        lens = len(s)\n",
    "        for i in range(lens):\n",
    "            if s[i] not in nowset:\n",
    "                nowset.add(s[i])\n",
    "            else:\n",
    "                ans += 1\n",
    "                nowset.clear()\n",
    "                nowset.add(s[i])\n",
    "        # if len(nowset) > 0:\n",
    "        #     ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c in vis:\n",
    "                ans += 1\n",
    "                vis = set([c])\n",
    "            else:\n",
    "                vis.add(c)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans=0\n",
    "        cur=''\n",
    "        for i in s:\n",
    "            if i not in cur:\n",
    "                cur+=i\n",
    "            else:\n",
    "                ans+=1\n",
    "                cur=i\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans=1\n",
    "\n",
    "        c=Counter()\n",
    "        for i in range (0,len(s)):\n",
    "            x=s[i]\n",
    "            c[x]+=1\n",
    "            if c[x]==2:\n",
    "                ans+=1\n",
    "                c=Counter()\n",
    "                c[x]=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        appear = set()\n",
    "        ans = 1\n",
    "        for c in s:\n",
    "            if c in appear:\n",
    "                appear.clear()\n",
    "                ans += 1\n",
    "            appear.add(c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count = 0\n",
    "        d = set()\n",
    "        for i in s:\n",
    "            if i not in d:\n",
    "                d.add(i)\n",
    "            else:\n",
    "                count += 1\n",
    "                d.clear()\n",
    "                d.add(i)\n",
    "        return count + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count=0\n",
    "        a=[]\n",
    "        for i in s:\n",
    "            if i in a :\n",
    "                a=[]\n",
    "                count+=1\n",
    "            a.append(i)\n",
    "        return count+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ret = 0\n",
    "        s1 = ''\n",
    "        for value in s:\n",
    "            if value in s1:\n",
    "                ret = ret + 1\n",
    "                s1 = ''\n",
    "            s1 += value\n",
    "\n",
    "        return ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        set_char = set()\n",
    "        num_substr = 1\n",
    "        for char in s:\n",
    "            if char in set_char:\n",
    "                set_char = set(char)\n",
    "                num_substr += 1\n",
    "            else:\n",
    "                set_char.add(char)\n",
    "        return num_substr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        current_chars = set()  # 用于跟踪当前子字符串中的字符\n",
    "        count = 0  # 子字符串的数量\n",
    "\n",
    "        for char in s:\n",
    "            if char in current_chars:\n",
    "                count += 1\n",
    "                current_chars.clear()\n",
    "            current_chars.add(char)\n",
    "\n",
    "        if current_chars:  # 如果还有剩余的字符，需要为其增加一个子字符串\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 1\n",
    "        hashtable = set()\n",
    "        hashtable.add(s[0])\n",
    "        for char in s[1:]:\n",
    "            if char not in hashtable:\n",
    "                hashtable.add(char)\n",
    "            else:\n",
    "                hashtable =set()\n",
    "                hashtable.add(char)\n",
    "                res +=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        current_chars = set()  # 用于跟踪当前子字符串中的字符\n",
    "        count = 0  # 子字符串的数量\n",
    "\n",
    "        for char in s:\n",
    "            if char in current_chars:\n",
    "                count += 1\n",
    "                current_chars.clear()\n",
    "            current_chars.add(char)\n",
    "\n",
    "        if current_chars:  # 如果还有剩余的字符，需要为其增加一个子字符串\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        left=0\n",
    "        ans=0\n",
    "        letterMapping={}\n",
    "        for i,c in enumerate(s):\n",
    "            if c in letterMapping:\n",
    "                if left<=letterMapping[c]:\n",
    "                    ans+=1\n",
    "                    left=i\n",
    "            letterMapping[c]=i\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        vis = \"\"\n",
    "        for ch in s:\n",
    "            if ch in vis:\n",
    "                vis = \"\"\n",
    "                ans += 1\n",
    "            vis += ch\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # dic = set()\n",
    "        # ans = 0\n",
    "        # for ch in s:\n",
    "        #     if ch in dic:\n",
    "        #         ans += 1\n",
    "        #         dic = set(ch)\n",
    "        #     else:\n",
    "        #         dic.add(ch)\n",
    "        # return ans + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cur = ''\n",
    "        res = 1\n",
    "        for i in s:\n",
    "            if i in cur:\n",
    "                res += 1\n",
    "                cur = i\n",
    "            else:\n",
    "                cur += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        vis = set()\n",
    "        for i, c in enumerate(s):\n",
    "            if c in vis:\n",
    "                vis.clear()\n",
    "                ans += 1\n",
    "            vis.add(c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 经典的滑动窗口\n",
    "        j, cnt, window = 0, 0, set()\n",
    "        while j < len(s):\n",
    "            if s[j] in window:  # 出现重复值\n",
    "                cnt += 1\n",
    "                window = set()  # 清空窗口\n",
    "            window.add(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  # 加上最后的一个区间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        temp = set()\n",
    "        for i in s:\n",
    "            if i not in temp:\n",
    "                temp.add(i)\n",
    "            else:\n",
    "                ans += 1\n",
    "                temp = set(i)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        dic={}\n",
    "        result=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]]=1\n",
    "            else:\n",
    "                result+=1\n",
    "                dic={s[i]:1}\n",
    "        \n",
    "        return result+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        集合 = set()\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            if i in 集合:\n",
    "                最少次数 += 1\n",
    "                集合.clear()\n",
    "            集合.add(i)\n",
    "        return 最少次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        j, cnt, window = 0, 0, {}\n",
    "        while j < len(s):\n",
    "            if s[j] in window: \n",
    "                cnt += 1\n",
    "                window = {}  \n",
    "            window[s[j]]=0\n",
    "            j += 1\n",
    "        return cnt + 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            t=set()\n",
    "            while i<n and s[i] not in t:\n",
    "                t.add(s[i])\n",
    "                i+=1\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 0\n",
    "        visit = set()\n",
    "        for c in s:\n",
    "            if c in visit:\n",
    "                res += 1\n",
    "                visit = set()\n",
    "            visit.add(c)\n",
    "        return res if visit == set() else res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            if ch in visited:\n",
    "                ans += 1\n",
    "                visited = set()\n",
    "            visited.add(ch)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cnt = 1\n",
    "        str_set = set()\n",
    "        for char in s:\n",
    "            if char in str_set:\n",
    "                cnt += 1\n",
    "                str_set.clear()\n",
    "            str_set.add(char)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        index = 0\n",
    "        cur = []\n",
    "        result = 0\n",
    "        while index < len(s):\n",
    "            if s[index] not in cur:\n",
    "                cur.append(s[index])\n",
    "            else:\n",
    "                result += 1\n",
    "                cur = []\n",
    "                continue\n",
    "            index += 1\n",
    "        if cur:\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        集合 = set()\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            if i in 集合:\n",
    "                最少次数 += 1\n",
    "                集合.clear()\n",
    "            集合.add(i)\n",
    "        return 最少次数\n",
    "        \"\"\"\n",
    "        #位运算\n",
    "        集合 = 0\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            i  = ord(i)-97\n",
    "            if 集合 >> i & 1:\n",
    "                最少次数 += 1\n",
    "                集合 = 0\n",
    "            集合 |= 1<<i\n",
    "        return 最少次数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        temp = [0] * 26\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            num = ord(s[i]) - ord(\"a\")\n",
    "            if temp[num] == 0:\n",
    "                temp[num] += 1\n",
    "            else:\n",
    "                del(temp)\n",
    "                res += 1\n",
    "                temp = [0] * 26\n",
    "                temp[num] = 1\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        '''\n",
    "        use set: \n",
    "        1. let res is result we want, temp = set()\n",
    "        2. iterate s:\n",
    "            (1)if charcter in set, then res + 1, and set temp to empty\n",
    "            (2) add charcter to set\n",
    "        3. return res +1\n",
    "\n",
    "        O(len(s))\n",
    "\n",
    "        '''\n",
    "\n",
    "        res = 0\n",
    "        temp = set()\n",
    "\n",
    "        for char in s:\n",
    "            if char in temp:\n",
    "                temp = set()\n",
    "                res += 1\n",
    "            temp.add(char)\n",
    "        \n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cont=0\n",
    "        n=len(s)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            if s[i] in dp:\n",
    "                dp.clear()\n",
    "                cont+=1\n",
    "            dp.append(s[i])\n",
    "        return cont+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cur = []\n",
    "        res = 1\n",
    "        for i, c in enumerate(s):\n",
    "            if c in set(cur):\n",
    "                res += 1\n",
    "                print(cur)\n",
    "                cur = []\n",
    "            cur.append(c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res, mark = 1, set()\n",
    "        for c in s:\n",
    "            if c in mark:\n",
    "                res += 1\n",
    "                mark.clear()\n",
    "            mark.add(c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 经典的滑动窗口\n",
    "        j, cnt, window = 0, 0, set()\n",
    "        while j < len(s):\n",
    "            if s[j] in window:  # 出现重复值\n",
    "                cnt += 1\n",
    "                window = set()  # 清空窗口\n",
    "            window.add(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  # 加上最后的一个区间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, t = 0, set()\n",
    "        for ch in s:\n",
    "            if ch not in t:\n",
    "                t.add(ch)\n",
    "            else:\n",
    "                ans += 1\n",
    "                t = set([ch])\n",
    "        if t:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        '''\n",
    "        use set: \n",
    "        1. let res is result we want, temp = set()\n",
    "        2. iterate s:\n",
    "            (1)if charcter in set, then res + 1, and set temp to empty\n",
    "            (2) if not, add charcter to set\n",
    "        3. return result\n",
    "\n",
    "        O(len(s))\n",
    "\n",
    "        '''\n",
    "\n",
    "        res = 0\n",
    "        temp = set()\n",
    "\n",
    "        for char in s:\n",
    "            if char in temp:\n",
    "                temp = set()\n",
    "                res += 1\n",
    "            temp.add(char)\n",
    "        \n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        d = defaultdict(int)\n",
    "        cnt = 1\n",
    "        left = 0\n",
    "        while left < len(s):\n",
    "            if d[s[left]] == 1:\n",
    "                d = defaultdict(int)\n",
    "                cnt += 1\n",
    "            d[s[left]] += 1\n",
    "            left += 1\n",
    "        return cnt                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        record = {}\n",
    "        count = 1\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if c not in record:\n",
    "                record[c]=1\n",
    "            else:\n",
    "                record = {}\n",
    "                record[c] = 1\n",
    "                count+=1\n",
    "\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        mask, res = 0, 1\n",
    "        ordA = ord('a')\n",
    "        for c in s:\n",
    "            m = 1<<(ord(c) - ordA)\n",
    "            if mask & m:\n",
    "                mask = 0\n",
    "                res += 1\n",
    "            mask |= m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        res = 0\n",
    "        hashset = set()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            hashset.add(s[i])\n",
    "            res += 1\n",
    "            \n",
    "            j = i + 1\n",
    "            while j < n and s[j] not in hashset:\n",
    "                hashset.add(s[j])\n",
    "                j += 1\n",
    "                \n",
    "            i = j\n",
    "            hashset.clear()\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count=1\n",
    "        temp=\"\"\n",
    "        for i in s:\n",
    "            if i not in temp:\n",
    "                temp+=i\n",
    "            else:\n",
    "                count+=1\n",
    "                temp=i\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        tmp_s = \"\"\n",
    "        cn = 0\n",
    "        for ss in s:\n",
    "            print(ss, tmp_s)\n",
    "            if ss not in tmp_s:\n",
    "                tmp_s = tmp_s + ss\n",
    "            else:\n",
    "                tmp_s = ss\n",
    "                cn += 1\n",
    "        if tmp_s != \"\":\n",
    "            return cn + 1\n",
    "        else:\n",
    "            return cn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        sub_s = set()\n",
    "\n",
    "        cnt = 1\n",
    "        for char in s:\n",
    "            if char not in sub_s:\n",
    "                sub_s.add(char)\n",
    "                print(sub_s, cnt)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                sub_s = set()\n",
    "                sub_s.add(char)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        my_dict = {}\n",
    "        count = 0\n",
    "        start = 0\n",
    "        for index, char in enumerate(s):\n",
    "            if char not in my_dict:\n",
    "                my_dict[char] = index\n",
    "            elif start > my_dict[char]:\n",
    "                my_dict[char] = index\n",
    "            else:\n",
    "                \n",
    "                count += 1\n",
    "                start = index\n",
    "                my_dict[char] = index\n",
    "                print(start)\n",
    "        if start <= len(s) - 1:\n",
    "            # results.append(s[start:])\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        arr = list(s)\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i] in arr[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "                # print(i)\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        base = 0\n",
    "        ans = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[base:i]:\n",
    "                ans += 1\n",
    "                base = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = []\n",
    "        tmp = \"\"\n",
    "        for i in s:\n",
    "            if i not in tmp:\n",
    "                tmp+=i\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp=i\n",
    "        res.append(tmp)\n",
    "        return(len(res))\n",
    "#        return(max(s.count(x) for x in s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        lst = ['']\n",
    "        l = len(s)\n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if s[i] not in lst[cnt]:\n",
    "                lst[cnt] += s[i]\n",
    "            else:\n",
    "                cnt +=1\n",
    "                lst.append(s[i])\n",
    "        return len(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        lst = ['']\n",
    "        l = len(s)\n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if s[i] not in lst[cnt]:\n",
    "                lst[cnt] += s[i]\n",
    "            else:\n",
    "                cnt +=1\n",
    "                lst.append(s[i])\n",
    "        return len(lst)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
